#include <stdio.h>
#include <stdlib.h>

#define FLAG -100

typedef int DataType;
typedef enum bool Bool;
enum bool
{
    false,
    true
};

struct ListNode
{
    DataType val;
    struct ListNode *next;
};
typedef struct ListNode *PNode;
typedef struct ListNode *LinkList;

LinkList createNullList_link(void)
{
    LinkList L = (LinkList)malloc(sizeof(struct ListNode));
    if (L == NULL)
    {
        printf("Out of memory!\n");
    }
    return L;
}

Bool ListIsEmpty(LinkList L)
{
    return L->next == NULL;
}

PNode locate_link(LinkList L, DataType x)
{
    PNode p;
    for (p = L; p != NULL; p = p->next)
    {
        if (p->val == x)
            return p;
    }
    return p;
}

Bool insertPost_link(LinkList L, PNode p, DataType x)
{
    PNode q = (PNode)malloc(sizeof(struct ListNode));
    q->val = x;
    // 先立新，再破旧.
    q->next = p->next;
    p->next = q;
    return true;
}

Bool insertPre_link(LinkList L, PNode p, DataType x)
{
    PNode q;
    for (q = L; q->next != p; q = q->next)
        ;
    // if (insertPost_link(L, q, x)){ }
    PNode a = (PNode)malloc(sizeof(struct ListNode));
    a->val = x;
    a->next = q->next;
    q->next = a;
    return true;
}

Bool deleteV_link(LinkList L, DataType x)
{
    PNode p;
    for (p = L; p != NULL; p = p->next)
    {
        if (p->next != NULL && p->next->val == x)
        {
            // 删除值为x的结点.
            PNode tmp = p->next;
            p->next = p->next->next;
            free(tmp);
        }
    }
    return true;
}

Bool deleteP_link(LinkList L, PNode p)
{
    PNode q;
    for (q = L; q->next != p; q = q->next)
        ;
    // 删除p结点，即删除q的下一结点.
    PNode tmp = q->next;
    q->next = q->next->next;
    free(tmp);
    return true;
}

LinkList createLinkList_H()
{
    LinkList L;
    PNode p;
    L = (LinkList)malloc(sizeof(struct ListNode));
    L->next = NULL;
    int x;
    scanf("%d", &x);
    while (x != FLAG)
    {
        p = (PNode)malloc(sizeof(struct ListNode));
        p->val = x;
        p->next = L->next;
        L->next = p;
        scanf("%d", &x);
    }
    return L;
}

void print_llist(LinkList L)
{
    PNode p;
    for (p = L->next; p != NULL; p = p->next)
    {
        printf("%d ", p->val);
    }
    printf("\n");
}

void sort(LinkList L){
	LinkList p,pre_L,q;
	p = L->next->next;		// 先保存下L的第二个元素，因为下一步要将L变成只有一个元素的有序表。  
	L->next->next = NULL;	// 将L变成只有一个元素的有序表
	// 从L的第二个元素开始遍历整个L直至表尾 
	while(p != NULL){
		q = p->next;
		pre_L = L;	// 先用pre_L来保存L,指向有序区域。
		while(pre_L->next !=NULL && pre_L->next->val < p->val) // 遍历pre_L所指向的有序表L，直至找到比p大的节点 
			pre_L = pre_L->next; 
        // 插入该结点
		p->next = pre_L->next;
		pre_L->next = p;
        // 让p指向待排序区域里下一个结点
		p = q;	
	} 
}

int main()
{
    LinkList L = createLinkList_H();
    print_llist(L);
    sort(L);
    print_llist(L);
    return 0;
}
